<!DOCTYPE html>
<html class="client-nojs vector-feature-night-mode-disabled vector-feature-language-in-header-enabled vector-feature-language-in-main-page-header-disabled vector-feature-page-tools-pinned-disabled vector-feature-toc-pinned-clientpref-1 vector-feature-main-menu-pinned-disabled vector-feature-limited-width-clientpref-1 vector-feature-limited-width-content-enabled vector-feature-custom-font-size-clientpref-1 vector-feature-appearance-pinned-clientpref-1 vector-sticky-header-enabled" lang="en" dir="ltr"><head>
<meta charset="UTF-8">
<title>Graphplan</title>
<meta name="viewport" content="width=device-width, initial-scale=1.0">
<link rel="canonical" href="https://en.wikipedia.org/wiki/Graphplan"> <link href="./mw/skins.vector.icons.css" rel="stylesheet" type="text/css">
<link href="./mw/skins.vector.search.codex.styles.css" rel="stylesheet" type="text/css">
<link href="./mw/skins.vector.styles.css" rel="stylesheet" type="text/css">
<link href="./mw/user.styles.css" rel="stylesheet" type="text/css">
<meta name="ResourceLoaderDynamicStyles" content="">
<link rel="stylesheet" type="text/css" href="./mw/site.styles.css">
<link rel="stylesheet" type="text/css" href="./mw/noscript.css">
<link rel="stylesheet" type="text/css" href="./footer.css">
<link rel="stylesheet" type="text/css" href="./vector-2022.css">
</head>
<body class="skin--responsive skin-vector skin-vector-search-vue mediawiki ltr sitedir-ltr mw-hide-empty-elt ns-0 ns-subject page-Graphplan rootpage-Graphplan skin-vector-2022 action-view">
<div class="mw-page-container">
<div class="mw-page-container-inner">
<div class="mw-content-container">
<main id="content" class="mw-body">
<header class="mw-body-header vector-page-titlebar">
<h1 id="firstHeading" class="firstHeading mw-first-heading">
<span id="openzim-page-title" class="mw-page-title-main"><span class="mw-page-title-main">Graphplan</span></span>
</h1>
</header>
<a id="top"></a>
<div id="bodyContent" class="vector-body ve-init-mw-desktopArticleTarget-targetContainer" aria-labelledby="firstHeading" data-mw-ve-target-container="">
<div id="mw-content-text" class="mw-body-content mw-content-ltr" lang="en" dir="ltr"><div class="mw-content-ltr mw-parser-output" lang="en" dir="ltr">
<p><b>Graphplan</b> is an <a href="Algorithm" title="Algorithm">algorithm</a> for <a href="Automated_planning" class="mw-redirect" title="Automated planning">automated planning</a> developed by <a href="Avrim_Blum" title="Avrim Blum">Avrim Blum</a> and Merrick Furst in 1995. Graphplan takes as input a planning problem expressed in <a href="Stanford_Research_Institute_Problem_Solver" title="Stanford Research Institute Problem Solver">STRIPS</a> and produces, if one is possible, a sequence of operations for reaching a goal state.
</p><p>The name <i>graph</i>plan is due to the use of a novel <i>planning <a href="Graph_(discrete_mathematics)" title="Graph (discrete mathematics)">graph</a></i>, to reduce the amount of search needed to find the solution from straightforward exploration of the <i>state space graph</i>.
</p><p>In the <i>state space graph</i>:
</p>
<ul><li>the nodes are possible states,</li>
<li>and the edges indicate reachability through a certain action.</li></ul>
<p>On the contrary, in Graphplan's <i>planning graph</i>:
</p>
<ul><li>the nodes are actions and atomic facts, arranged into alternate levels,</li>
<li>and the edges are of two kinds:
<ol><li>from an atomic fact to the actions for which it is a condition,</li>
<li>from an action to the atomic facts it makes true or false.</li></ol></li></ul>
<p>The first level contains true atomic facts identifying the initial state.
</p><p>Lists of incompatible facts that cannot be true at the same time and incompatible actions that cannot be executed together are also maintained.
</p><p>The algorithm then iteratively extends the planning graph, proving that there are no solutions of length l-1 before looking for plans of <a href="Length" title="Length">length</a> l by backward chaining: supposing the goals are true, Graphplan looks for the actions and previous states from which the goals can be reached, pruning as many of them as possible thanks to incompatibility information.
</p><p>A closely related approach to planning is the Planning as Satisfiability (<a href="Satplan" title="Satplan">Satplan</a>). Both reduce the automated planning problem to search for plans of different fixed horizon lengths.
</p>
<div class="mw-heading mw-heading2"><h2 id="References">References</h2></div>
<ul><li>A. Blum and M. Furst (1997). <b><a rel="nofollow" class="external text" href="http://www.sciencedirect.com/science/article/pii/S0004370296000471">Fast planning through planning graph analysis</a></b>. Artificial intelligence. 90:281-300.</li></ul>
<div class="mw-heading mw-heading2"><h2 id="External_links">External links</h2></div>
<ul><li><a rel="nofollow" class="external text" href="https://www.cs.cmu.edu/~avrim/graphplan.html">Avrim Blum's Graphplan home page</a></li>
<li><a rel="nofollow" class="external text" href="http://www.philippe-fournier-viger.com/plplan.html">PLPLAN: A Java GraphPlan Implementation</a></li>
<li><a rel="nofollow" class="external text" href="http://nplanner.codeplex.com">NPlanner: A .NET GraphPlan Implementation</a> <a rel="nofollow" class="external text" href="https://web.archive.org/web/20131231195113/http://nplanner.codeplex.com/">Archived</a> 2013-12-31 at the <a href="Wayback_Machine" title="Wayback Machine">Wayback Machine</a></li>
<li><a rel="nofollow" class="external text" href="https://emplan.sourceforge.net/">Emplan and JavaGP: C++ and Java implementations of Graphplan</a></li>
<li><a rel="nofollow" class="external text" href="http://ocw.mit.edu/courses/electrical-engineering-and-computer-science/6-825-techniques-in-artificial-intelligence-sma-5504-fall-2002/lecture-notes/Lecture12FinalPart1.pdf">MIT OpenCourseWare lecture on GraphPlan and making planning graphs</a></li></ul></div><!--htdig_noindex--><div><div class="zim-footer">
This article is issued from <a class="external text" title="Last edited on 2024-08-27" href="https://en.wikipedia.org/wiki/?title=Graphplan&oldid=1242556086">Wikipedia</a>. The text is available under <a class="external text" href="https://creativecommons.org/licenses/by-sa/4.0/deed.en">Creative Commons Attribution-Share Alike 4.0</a> unless otherwise noted. Additional terms may apply for the media files.
</div>
</div><!--/htdig_noindex--></div>
</div>
</main>
</div>
</div>
</div>
</body></html>